package JianZhiOffer;

import JianZhiOffer.entity.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * <p>
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 */
public class Solution07 {

    /**
     * 使用递归的方式
     * 1、前序的第一个元素为根节点root
     * 2、找到中序root对应的位置，那么则知道左子树有多少个节点，右子树有多少个节点
     * 3、这里使用分治的思想，把【左边的前序中序数组】和【右边的前序中序数组】继续递归下去，继续执行1、2。
     * 4、root.left = 左边递归结果；root.right = 右边递归结果
     * 5、终止条件为preStart > preEnd || inStart > inEnd
     * */

    // 把中序存储到map方便获取下标
    static Map<Integer, Integer> indexMap = new HashMap<>();
    static int[] preorder;

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || preorder.length != inorder.length) return null;

        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }

        Solution07.preorder = preorder;

        return confirmRoot(0, preorder.length - 1, 0, inorder.length - 1);
    }

    private static TreeNode confirmRoot(int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) return null;

        // 前序第一个为根节点
        int rootVal = preorder[preStart];
        TreeNode rootNode = new TreeNode(rootVal);
        // 获取中序的下标
        Integer index = indexMap.get(rootVal);

        TreeNode leftNode = confirmRoot(preStart + 1, preStart + (index - inStart), inStart, index - 1);
        TreeNode rightNode = confirmRoot(preStart + (index - inStart) + 1, preEnd, index + 1, inEnd);
        rootNode.left = leftNode;
        rootNode.right = rightNode;
        return rootNode;
    }


    public static void main(String[] args) {
        TreeNode treeNode1 = buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        TreeNode treeNode2 = buildTree(new int[]{3, 9, 8, 20, 15, 7}, new int[]{9, 8, 3, 15, 20, 7});
        System.out.println(treeNode1);
        System.out.println(treeNode2);


    }
}
